package search;
import java.util.*;
/**
 * This abstract class is nused tp represent arbitrary node labelled and edge labelled
 * digraphs representing the state space for a problem.
 * 
 * @author Rudi Lutz 
 * @version 1.0
 */

public abstract class Digraph<N extends GraphNode<?>, E extends GraphEdge<?, N>>
{
    protected ArrayList<N> nodes;
    protected ArrayList<E> edges;
    //protected HashMap<N,ArrayList<E>> nodeEdges;
    
    /**
     * creates an empty digraph
     */
    public Digraph()
    {
        nodes = new ArrayList<N>();
        edges = new ArrayList<E>();
        //nodeEdges = new HashMap<N,ArrayList<E>>();
    }
    
    /**
     * adds a node to the digraph - it is only added if the node is not already present
     * @param n the node to be added 
     */
    public void addNode(N n)
    {
        if (!nodes.contains(n)) {
            nodes.add(n);
            //nodeEdges.put(n, new ArrayList<E>());
        }
    }
    
    /** adds an edge, provided it is not already present. If necessary it also adds 
     * the nodes at each end of the edge. So a digraph could be built up by simply adding edges.
     * @param edge the edge to be added
     */
    public void addEdge(E edge)
    {
        if (!edges.contains(edge)) {
            edges.add(edge);
            addNode(edge.getNode1());
            addNode(edge.getNode2());
            N node = edge.getNode1();
            //nodeEdges.get(node).add(edge);
            associateEdgeWithNode(edge,node);
        }
    }
    
    /**returns the nodes which are already known about. Bear in mind however that
     * in many applications the graph will grow dynamically
     */
    public List<N> getNodes()
    {
        return nodes;
    }
    
    /**
     * returns the edges known to be in the graph so far. however bear in mind the graph may grow dynamically in
     * some applications.
     */
    public List<E> getEdges()
    {
        return edges;
    }
    
    /**associates an edge with a node. This is application specific, largely depending 
     * on exactly how a particular implementation chooses to represent the information
     * about which edges go with which node. this depends largely on whether edges
     * and nodes are computed dynamically as needed, or are all known in advance, and added
     * specifically in advance. Because this is application specific this is an abstract 
     * method which must be provided in a concrete implementation.
     */
    public abstract void associateEdgeWithNode(E edge, N node);
    
    /**
     * returns the edges leaving a node. because this depends on the application (see
     * documentation for makeFindable() this is abstract and must be provided for a concrete implementation
     */
    public abstract List<E> getEdges(N node);
    //{
        //return nodeEdges.get(node);
    //}
    
    /**
     * returns the successor nodes to a given node
     */
    public List<N> getSuccessors(N node) {
        ArrayList<N> list = new ArrayList<N>();
        List<E> edges = getEdges(node);
        for (E edge : edges) {
            list.add(edge.getOppositeEnd(node));
        }
        return list;
    }
    
    /**
     * accepts a SearchVisitor, which then searches the graph
     */
    public SearchNode<N> accept(SearchVisitor<N,E> v)
    {
        return v.search(this);
    }
        
}
